package J.算法.滑动窗口;

import java.util.ArrayDeque;
import java.util.Deque;

public class _239滑动窗口最大值 {

    /**
     * 扩大操作：判断是不是大于当前最大值
     * 何时开始缩小：当窗口长度= k 时，
     * 缩小的时候就要返回结果了
     * 缩小操作：判断是不是最大数值 进行更新
     *
     * 如何维持一个最大列表？
     * 借助双端队列==
     *
     * 思路：in>队尾元素  队尾逐步pop 直到找到比他大的数，in<队尾 就从尾巴进去就好
     *      右移出的第一个元素 如果 是队头第一个 那么就对头弹出
     *
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length-k+1];
        int count =0;
      //  deque.add(Integer.MIN_VALUE);
      //  boolean end = false;

        int left=0,right =0;
        while (right< nums.length){

            int in = nums[right];
            right++;
            //操作

            while (!deque.isEmpty() && in > deque.peekLast() ){
                deque.pollLast();
            }
            deque.offerLast(in);


            while (right-left == k){

                res[count++] = deque.peekFirst();

                int out = nums[left];
                left++;

                if (out == deque.peekFirst()){
                    deque.pollFirst();
                }

            }

        }

        return res;

    }
}
